package _11_整理题目._2_二叉树_递归_dfs_bfs;


import org.junit.Test;
import util.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
 * 
 * _04_重建二叉树 和 _01_求二叉树的层序遍历  的组合
 * 
 */
public class _04_输出二叉树的右视图 {
    
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root = recover(xianxu, zhongxu);
        int[] result = printView(root);
        return result;
    }
    
    private TreeNode recover(int[] pre, int[] in) {
        if(pre.length==0 || in.length==0) return null;
        
        TreeNode root = new TreeNode(pre[0]);
        for(int i=0; i<in.length; i++) {
            if(in[i] == pre[0]) {
                root.left  = recover(Arrays.copyOfRange(pre,1,i+1), Arrays.copyOfRange(in,0,i));
                root.right = recover(Arrays.copyOfRange(pre,i+1,pre.length), Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        
        return root;
    }
    
    private int[] printView(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        List<Integer> result = new ArrayList<>();
        while(!queue.isEmpty()) {
            int n = queue.size();
            for(int i=0; i<n; i++) {
                TreeNode node = queue.poll();
                if(i == n-1) {
                    result.add(node.val);
                }
                if(node.left != null)  queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
        }
        
        return result.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    @Test
    public void main() {
        int[] pre = {1,2,3,4,5,6,7};
        int[] in  = {3,2,4,1,6,5,7};
        int[] rightView = solve(pre, in);
        System.out.println(Arrays.toString(rightView));
    }
    
}
